The present invention generally relates to digital multiplying circuits, and more particularly to a digital multiplying circuit which multiples an arbitrary multiplying constant including zero to an h-bit vector which is an element of a finite field (Galois field) GF(2.sup.h) by use of multipliers and data selectors, where h is a natural number.
A digital multiplying circuit for multiplying an arbitrary multiplying constant to a digital data, is conventionally used for various purposes. For example, in the field of data transmission such as data communication, PCM recorder and digital and audio discs, an error correction code is used to correct a code error in the transmitted data and restore the transmitted data into the correct data. The digital multiplying circuit is used to generate a check vector which constitutes the error correction code. The error correction code comprises the check vector and the data which is to be transmitted, which data is a generating element of the check vector, and various kinds of error correction codes are conventionally known. Among the various error correction codes, the Reed Solomon code has superior correcting capability and redundancy (the proportion of the check vector with respect to the check vector and the data to be transmitted) of the transmitting information. A description will now be given with respect to a multiplying circuit in a Reed Solomon code generating circuit.
First, the conventional principle for generating the Reed Solomon code will be described. A code word (block) of the Reed Solomon code is described by the following row matrix (1), where d.sub.1 through d.sub.m represent m h-bit data vectors which are to be transmitted, P.sub.0 through P.sub.n represent n h-bit check vectors, and h, m, and n are natural numbers. EQU [d.sub.1 d.sub.2 . . . d.sub.m P.sub.0 P.sub.1 . . . P.sub.n ](1)
In the Reed Solomon code defined in the finite field (Galois field) GF(2.sup.h), each of the above vectors is an element of the finite field GF(2.sup.h), and it is know that the following condition (2)must be satisfied among h, m, and n. EQU 2.sup.h -1.gtoreq.m+n+1 (2)
At the time of transmission (including recording), the check vectors P.sub.0 through P.sub.n are added with respect to the data vectors d.sub.1 through d.sub.m. The check vectors P.sub.0 through P.sub.n are generated so as to satisfy the following equation (3), where .alpha. represents a primitive element of the finite field GF(2.sup.h). ##EQU1##
When the above equation (3) may be rewritten as the following equations (4), where the symbol ".sym." represents an addition in the finite field GF(2.sup.h) and the symbol " " represents a multiplication in the finite field GF(2.sup.h). ##EQU2## A check matrix H.sub.0 is a matrix of the (n+1)-th row and the (m+n+1)-th row in the left (upper) term of the equation (3), and may be described by the following equation (5). ##EQU3## The following check matrix H.sub.0 ' is obtained when an operation of adding a predetermined row of the matrix described by the equation (5) which predetermined row is multiplied by a certain constant and another predetermined row of the matrix which other predetermined row is multiplied by a certain constant, is performed several times. ##EQU4## Since H.sub.0 ' is also a check matrix, the following equation (7) stands. ##EQU5## From the equations (6) and (7), it is hence possible to obtain the check vectors P.sub.0 through P.sub.n. ##EQU6## In the equations (8-1) through (8-n+1), .beta..sub.0(m+n) through .beta..sub.n(n+1) are m(n+1) constant vectors.
In the conventional Reed Solomon code generating circuit, the check vectors P.sub.0 through P.sub.n are generated based on the equations (8-1) through (8-n+1). A digital multiplying circuit is provided within the conventional circuit in order to multiply the constant vectors .beta..sub.0(m+n) through .beta..sub.n(n+1) with the data vectors d.sub.1 through d.sub.m in the equations (8-1) through (8-n+1). Conventionally, a first type of the digital multiplying circuit employs a read only memory (ROM) which pre-stores a table of m values obtained by multiplying .beta..sub.k(m+n) through .beta..sub.k(n+1) to corresponding arbitrary data vectors of the finite field GF(2.sup.h). A second type of the conventional digital multiplying circuit employs a first ROM which pre-stores a logarithmic table, an adding circuit, and a second ROM which pre-stores an antilogarithm table.
However, in order to pre-store the m values obtained by multiplying .beta..sub.k(m+n) through .beta..sub.k(n+1) to corresponding arbitrary data vectors of the finite field GF( 2.sup.h), the ROM of the first type of digital multiplying circuit must have a large memory capacity. For example, in a case where h=8, m=28, and n=3, that is, in the case of a (32, 28) Reed Solomon code in the finite field GF(2.sup.8), it is necessary to provide four ROMs within the Reed Solomon code generating circuit because the check matrix H.sub.0 ' is a four row by thirty-two column matrix as may be seen from the equation (6) and each of the vectors which are elements of the finite field GF(2.sup.8) comprises eight bits. Each ROM is supplied with an 8-bit vector input and a 5-bit column control signal required for discriminating the thirty-two columns, and is designed to produce an 8-bit vector. Hence, each ROM must have a memory capacity of 65,536 (=8.times.2.sup.13) bits. However, with the present integrated technology, it is difficult to manufacture a ROM having such a large memory capacity in the form of a large scale integrated (LSI) circuit with the present LSI technology, and the manufacturing cost of the LSI ROM circuit is extremely high.
On the other hand, the second type of digital multiplying circuit comprises two ROMs and an adding circuit as described before. In a case where h=8, the two ROMs are each constituted by 256.times.8 gates when the ROMs are manufactured in the form of LSI circuits. The adding circuit is constituted by approximately 200 gates when the adding circuit is manufactured in the form of an LSI circuit. Hence, it is also difficult to manufacture the second type of digital multiplying circuit in the form of an LSI circuit.